1. Field of the Invention
The present invention generally relates to the field of nonlinear optimization and, more particularly, to resource allocation, as for example, buffer pool optimization in computer database software where only the marginal utility is known.
2. Background Description
Conventionally, resource allocation maximizing some utility function using nonlinear optimization requires knowledge of the utility as a function of the allocated resources. For example, the resources could be the memory allocated to a series of computer processors and the utility is the aggregate performance of these processors or the reduction in power consumption of these processors. In prior art methods for solving this problem, knowledge of this utility function is required. Almost all prior art algorithms for solving this problem can be classified into one of the following three classes:                1. Only the utility function ƒ is known, i.e., at each point, there is a procedure to evaluated ƒ (x). Examples of such algorithms include the simplex method and genetic algorithms.        2. Only the utility function ƒ and the gradient ∇ƒ are known. Examples include steepest descent, conjugate gradient and Quasi-Newton methods.        3. The utility function ƒ, its gradient ∇ƒ and its Hessian ∇2ƒ are known. Examples include Newton's method.        
Thus, in prior art algorithms, knowledge of the utility function is required in order to solve the optimization problem. In some applications, knowledge of this utility function is absent, and prior art iterative optimization algorithms cannot be used to solve this problem.
As a specific example, buffer pool optimization in International Business Machines' (IBM's) DB2 computer database software is a problem where only the gradient of the utility function is known, i.e., at each point we know the benefit in terms of saved disk access time due to allocating more memory, but the utility, which in this case is the total saved disk access time due to current buffer pool setting, is unknown.
Therefore, there is a need in the art for a method to allocate resources maximizing such utility using algorithms which do not need to know the utility as a function of the resources.